package bintree.heap;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.NoSuchElementException;

/**
 * 基于动态数组实现的 最大堆
 */
public class MaxHeap {
    // 实际储存元素的数组
    private  List<Integer> elementData;
    // 当前堆中元素的个数
    private int size;

    //无参构造，默认创建数组大小为 10
    public MaxHeap(){
        this(10);
    }

    //有参构造--设置数组大小
    public MaxHeap(int n) {
        this.elementData = new ArrayList<>(size);
    }

    /**
     * 原地堆化，创建一个构造方法。
     * 降任意的整形数组arr 调整了堆
     */
    public MaxHeap(int[] arr){
        this.elementData = new ArrayList<>(arr.length);//开辟等长的空间
        //1. 先将所有元素复制到 Data数组中
        for(int i : arr){
            elementData.add(i);
            size ++;
        }
        //2. 从最后一个非叶子节点不断进行siftDown操作
        // 最后一个非叶子节点就是最后一个元素的父节点
        for (int i = parent(size - 1); i >= 0 ; i--) {
            //不断下层操作
            siftDown(i);
        }
    }


    //添加元素
    public void add(int val){
        //1.直接向数组末尾添加元素
        elementData.add(val);
        size ++;
        //2. 进行元素的上浮操作,设计一个方法
        siftUp(size - 1);
    }

    /**
     * 取中当前最大堆的最大值
     */
    public int extractMax(){
        //如果此时的数组为空，那么就报一个异常警告
        if(isEmpty()){
            throw new NoSuchElementException("heap is empty!cannot extract!");
        }
        //不为空，说明此时树根就是最大节点
        int max = elementData.get(0);
        //将数组末尾元素顶到堆顶
        elementData.set(0, elementData.get(size - 1));
        // 将数组的最后一位元素从堆中删除
        elementData.remove(size - 1);
        size --;
        //进行元素的下层操作，从索引为 0 的根开始
        siftDown(0);
        return max;
    }

    /**
     * 从索引k开始进行元素的下沉操作
     */
    private void siftDown(int k) {
        //因为这堆满足完全二叉树特性，不存在有右子树，没有左子树
        //循环条件表示：当前还存在有子树，可以循环判断是否能下层
        while(leftChild(k) < size){
            //获取左子树的索引
            int j = leftChild(k);//用来进行下层交换的索引值
            // 表示此时也存在右子树  左子树和右子树索引差 1
            if(j + 1 < size) {
                //判断此时的右子树是否大于左子树的值
                if (elementData.get(j + 1) > elementData.get(j)) {
                    //表示右子树大于左子树，更新 j 索引值，变成右子树的索引
                    j++;
                }
            }

            //此时的索引 j 一定对应了左右子树中的最大值索引
            //判断索引 k元素是否需要进行下层操作
            if (elementData.get(k) < elementData.get(j)) {
                //说明需要进行下层
                swap(k, j);
                //更新此时需要下层元素的索引
                k = j;
            } else {
                // 当前元素 >= 左右子树最大值，下沉结束，元素k落在了最终位置
                break;
            }



        }//while
}


    //传入需要进行上浮操作元素的索引
    private void siftUp(int k) {
        //小于父类节点和已经是最大根节点就结
                          // 上浮元素节点值  跟它的 父类节点值比较
        while(k > 0 && elementData.get(k) > elementData.get(parent(k)) ){
            //进行节点值交换
            swap(k, parent(k));
            //进行交换后，k节点的父类节点就是新的上浮元素
            k = parent(k);//更新上浮元索引
        }

    }

    // 交换两个数字索引节点值
    private void swap(int k, int parent) {
        int child = elementData.get(k);//保存k节点的val
        int pareentVal = elementData.get(parent);//k的父类节点值val
        elementData.set(k,pareentVal);//k索引处更换为父类值
        elementData.set(parent, child);//父类索引处更换为 k的val值
    }

    /**
     * 传入数组的索引，找到节点k对应的父类的索引
     */
    private int parent(int k){
        //规则：(k - 1) / 2 ,右移相当于除以 2
        return (k - 1) >> 1;
    }

    /**
     * 找对节点 k对应的 左子树的索引
     * (2 * k) + 1
     */
    public int leftChild(int k){
        return (k << 1) + 1;
    }

    /**
     * 找对节点 k对应的 右子树的索引
     * (2 * k) + 2
     */
    public int rightChild(int k){
        return (k << 1) + 2;
    }

    //返回当前数组的元素个数
    public int getSize(){
        return size;
    }

    //判断数组现在是否为 空
    public boolean isEmpty(){
        return size == 0;
    }

    //toStrng方法实现
    @Override
    public String toString() {
        return elementData.toString();
    }

    //查看当前数组的最大元素
    public int peekMax(){
        if(isEmpty()){
            throw new NoSuchElementException("heap is empty!cannot peek!");
        }
        return elementData.get(0);
    }


}
